package com.kaizen.leet11;

/**
 * 11. 盛最多水的容器
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 说明：你不能倾斜容器，且 n 的值至少为 2。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/container-with-most-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author kaizen
 * @date 2020/4/20 23:28
 */
public class SolutionKaizen {

    /*
     * 暴力破解循环找出 更新最大面积，同时更新记录 i1和i2的位置
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        // 说明：你不能倾斜容器，且 n 的值至少为 2。
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            for (int h = 1; h < height.length; h++) {
                maxArea = Math.max((h-i) * Math.min(height[h], height[i]), maxArea);
            }
        }
        return maxArea;
    }

    /**
     * 双指针解法
     * 在每一个状态下，无论长板或短板收窄 1 格，都会导致水槽 底边宽度 -1
     * 此时只要判断哪边的高度较低 则指针向前移动继续尝试
     *
     */
    public int maxArea2(int[] height) {
        int maxArea = 0;
        int l = 0,r = height.length-1;
        while (r != l) {
            if (height[l] <=  height[r]) {
                maxArea = Math.max((r-l) * height[l], maxArea);
                l++;
            }else {
                maxArea = Math.max((r-l) * height[r], maxArea);
                r--;
            }
        }
        return maxArea;
    }
}
